Many computer simulations must be capable of detecting collisions between bodies or objects in the simulation to realistically portray effects such as deflections. To this end, prior art collision detection system take the positions of N objects as inputs, and report which pairs of objects are in contact with each other, One brute force technique to this problem tests each possible pair of objects in the simulation for contact with one another. Under this approach, in a simulation containing N objects, the number of tests performed is:
      (                            n                                      2                      )    =            n      ⁡              (                              n            -            1                    2                )              .  
The time needed to complete this test is O(N2) (which is pronounced “big Oh of N squared”) which means that there exists positive constants c and n0 such that, for N greater than or equal to n0 the run time of the test is less than or equal to cN2. This is true because, if objects are moved (as would happen, for example, between frames of an animated movie or other computer simulation), all N(N−1)/2 calculations must be repeated to test for collisions between the objects in their new positions.
An existing technique, known as “sweep and prune,” can be used to reduce the average run-time of this brute force technique to O(N) per frame. Sweep and prune exploits the spatial coherency between frames in the simulation. More specifically, in most simulations, objects move a small distance between frames. Therefore, the information used to detect collisions in one frame can be reused in seeking collisions in the next frame.
Sweep and prune employs three sorted lists, one for each axis (e.g. the X, Y and Z axes) in a given coordinate system. Each of the lists contain the projections of each object onto the list's corresponding axis. Because objects tend to move only a small distance between each time interval, the lists can be resorted in O(N) time using the well known insertion sort algorithm (assuming an initial sort has been completed). Once sorted, each list is reviewed to determine which, if any, pairs of object projections overlap on the associated axis. Finally, a set of potentially colliding objects is generated by finding all pairs of objects that overlap in all three lists. An exact test for collision may then be performed on the pairs of objects in this set.
While the average run time for sweep and prune is O(N) for many applications of collision detection, there are important and common exceptions where the average running time of sweep and prune degrades to O(N2). To consider some examples, let the sorted lists of object projections onto the X, Y and Z axes be Lx, Ly, and Lz, respectively. The set SI is the set of object pairs generated by processing list LI, were I is X, Y, or Z. The set S is defined to be the intersection of the sets Sx, Sy, and Sz. The set S is the final set of potentially colliding pairs of objects produced by sweep and prune.
Collisions are rare events. Thus, the number of collisions expected per frame is much less than the number of objects in the simulation. However, if the distribution of objects in the simulation and the coordinate system used in sweep and prune are aligned in some fashion, then at least one of the sets SI found by processing the lists LI will be larger than the number of objects N in the simulation. For example, if all of the objects exist in the XY plane, then all of the objects have overlapping projections onto the Z axis. Thus, when the list Lz, is processed, the set Sz will contain n(n−1)/2 pairs of potentially colliding objects. As a result, the running time of sweep and prune degrades to O(N2). Since in many simulations objects tend to reside in a plane, the average run time of sweep and prune tends to be O(N2).
Sweep and prune will also run in O(N2) time if the objects in the simulation are collinear along a line parallel to one of the X, Y or z axes.